package offer

/*
时间复杂度:O(4^n/(根号N))
空间复杂度:O(N) 最多递归2N层,
*/

func generateParenthesis(n int) []string {
	res := new([]string)
	backtrack(n, n, "", res)
	return *res
}

func backtrack(left, right int, tmp string, res *[]string) {
	if right == 0 {
		*res = append(*res, tmp)
	}
	if left > 0 {
		// 注意: 这里传入的是tmp+"(", tmp本身的值没有变化
		// 当tmp为"("时,这里传入的是"((",但是 if right > left中传入的是 "()"
		backtrack(left-1, right, tmp+"(", res)
	}
	if right > left {
		backtrack(left, right-1, tmp+")", res)
	}
}
